home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 322_01 / btree.c < prev    next >
C/C++ Source or Header  |  1990-08-04  |  15KB  |  831 lines
  1. /***
  2.  
  3. * module name:
  4.     btree.c
  5. * function:
  6.     Provide a library of routines for creating and manipulating
  7.     B-Trees.  The "order" of the B-Tree is controlled by a manifest
  8.     constant.
  9.  
  10.     This module runs stand-alone with a dummy main program
  11.     if the symbol STAND_ALONE is defined.
  12. * interface routines:
  13.     BTREE
  14.     Insert(dtm, tree)    Insert DATUM dtm into B-tree "tree",
  15.                 returning a reference to the updated
  16.                 tree.
  17.     BTREE
  18.     Delete(key, tree)    Remove the entry associated with "key"
  19.                 from the B-Tree.  Returns a reference
  20.                 to the updated tree.
  21.     
  22.     DATUM *
  23.     Search(key, tree)    Look for key "key" in B-tree "tree".
  24.                 Return a reference to the matching
  25.                 DATUM if found, else NULL.
  26.  
  27.     Apply(t, func)        Applies function "func" to every cell
  28.                 in the B-Tree -- uses an inorder
  29.                 traversal.
  30. * libraries used:
  31.     standard
  32. * compile time parameters:
  33.     cc -O -c btree.c
  34. * history:
  35.     Richard Hellier, University of Kent at Canterbury,
  36.     working from "Algorithms+Data Structures = Programs"
  37.     by N.Wirth -- also, "Data Structures and Program Design" by B.Kruse
  38.     Pub. Prentice-Hall.
  39.  
  40.     Modified for use in dynamic memory allocation leak trace tool
  41.     by Mike Schwartz, 3-20-87.  We call mmalloc and ffree instead of
  42.     malloc and free here, since malloc and free call this btree package
  43.     in the dynamic memory allocation leak detection package.
  44.  
  45. ***/
  46.  
  47. #include "btree.h"
  48.  
  49. DATUM    NullDatum = {
  50.     (char *) NULL,
  51. };
  52.  
  53. static BTREE        NewNode;
  54.  
  55.  
  56. /*
  57. **  ERROR -- Print an error message
  58. **
  59. **    Write the error text to the
  60. **    standard error stream.
  61. **
  62. **    Parameters:
  63. **        fmt       --  Printf-style format string
  64. **        arg[1-3]  --  Arguments as needed.
  65. **
  66. **    Returns:
  67. **        None.
  68. **
  69. */
  70.  
  71. /* ARGSUSED */
  72.  
  73. Error(fmt, arg1, arg2, arg3)
  74. char    *fmt;{
  75.     fprintf(stderr, fmt, arg1, arg2, arg3);
  76. }
  77.  
  78. /*
  79. **  KEYCMP -- Compare two key values
  80. **
  81. **    Like "strcmp" but use key
  82. **    values rather than strings.
  83. **
  84. **    Parameters:
  85. **        key1  --  First key,
  86. **        key2  --  Second key.
  87. **
  88. **    Returns:
  89. **        -1 if key1 < key2;
  90. **        0  if key1 = key2;
  91. **        1  if key1 > key2;
  92. **
  93. */
  94.  
  95. KeyCmp(key1, key2)
  96. KEY    key1,
  97.     key2;{
  98.  
  99.     return key1 < key2 ? -1 : key1 == key2 ? 0 : 1;
  100. }
  101.  
  102. /*
  103. **  SHOWDATUM -- Display a datum
  104. **
  105. **    Atomic routine used to display
  106. **    the contents of a datum.
  107. **
  108. **    Parameters:
  109. **        datum  --  Datum to print.
  110. **
  111. **    Returns:
  112. **        None.
  113. **
  114. */
  115.  
  116. ShowDatum(dtm)
  117. DATUM    dtm;{
  118.     printf("\tkey x%x: callnum %d, size %d\n", dtm.key, dtm.inf.MalCallNum,
  119.         dtm.inf.MalSize);
  120. }
  121.  
  122. /*
  123. **  MKNODE -- Make a new B-tree node
  124. **
  125. **    Allocate storage for a new B-tree node
  126. **    and copy in some pointers.
  127. **
  128. **    Parameters:
  129. **        k1  --  First key value,
  130. **        p0  --  First ptr,
  131. **        p1  --  Second ptr.
  132. **
  133. **    Returns:
  134. **        Reference to the new node.
  135. **
  136. */
  137.  
  138. BTREE
  139. MkNode(dtm, p0, p1)
  140. DATUM    dtm;
  141. BTREE    p0,
  142.     p1;{
  143.     char    *mmalloc();
  144.     BTREE    t;
  145.  
  146.     t = (BTREE) mmalloc(sizeof(NODE));
  147.  
  148.     t -> t_ptr [0] = p0;
  149.     t -> t_ptr [1] = p1;
  150.     t -> t_dat [0] = dtm;
  151.     t -> t_active  = 1;
  152.  
  153.     return t;
  154. }
  155. /*
  156. **  DISPOSE -- Dispose of a tree node
  157. **
  158. **    Return the storage occupied by the
  159. **    tree node to the pool.
  160. **
  161. **    Parameters:
  162. **        t  --  Ptr to the tree node.
  163. **
  164. **    Returns:
  165. **        None.
  166. **
  167. */
  168.  
  169. Dispose(t)
  170. BTREE    t;{
  171.     ffree((char *) t);
  172. }
  173.  
  174. /*
  175. **  INSINNODE -- Add a key to a node
  176. **
  177. **    Add a key value into a
  178. **    B-tree node.  Splitting of
  179. **    nodes is handled elsewhere.
  180. **
  181. **    Parameters:
  182. **        t   --  Ptr to the node,
  183. **        key --  Key value to enter,
  184. **        ptr --  Link to subordinate node.
  185. **
  186. **    Returns:
  187. **        None.
  188. **
  189. */
  190.  
  191. InsInNode(t, d, ptr)
  192. BTREE    t,
  193.     ptr;
  194. DATUM    d;{
  195.     int    i;
  196.  
  197.     for ( i = t -> t_active; i > 0 && KeyCmp(d . key, t -> t_dat [i-1] . key) < 0; i--) {
  198.         t -> t_dat [i]     = t -> t_dat [i - 1];
  199.         t -> t_ptr [i + 1] = t -> t_ptr [i];
  200.     }
  201.  
  202.     t -> t_active++;
  203.     t -> t_dat [i]   = d;
  204.     t -> t_ptr [i+1] = ptr;
  205. }
  206.  
  207. /*
  208. **  INTERNALINSERT -- Key insert routine proper
  209. **
  210. **    The business end of the key insertion
  211. **    routine.
  212. **
  213. **    Parameters:
  214. **        key  --  Key to insert,
  215. **        t    --  Tree to use.
  216. **
  217. **    Returns:
  218. **        Value of the key inserted.
  219. **
  220. */
  221.  
  222. DATUM
  223. InternalInsert(dtm, t)
  224. DATUM    dtm;
  225. BTREE    t;{
  226.     int    i,
  227.         j;
  228.     DATUM    ins;
  229.     BTREE    tmp;
  230.  
  231.     if (t == NULL) {
  232.         NewNode = NULL;
  233.         return dtm;
  234.     } else {
  235.         for (i = 0; i < t -> t_active && KeyCmp(t -> t_dat [i] . key, dtm . key) < 0; ++i)
  236.             ;        /* NULL BODY */
  237.         if (i < t -> t_active && KeyCmp(dtm . key, t -> t_dat [i] . key) == 0)
  238.             fprintf(stderr, "Already had it!\n");
  239.         else {
  240.             ins = InternalInsert(dtm, t -> t_ptr [i]);
  241.  
  242.             if (KeyCmp(ins . key, NullDatum . key) != 0)
  243.                 if (t -> t_active < 2 * M)
  244.                     InsInNode(t, ins, NewNode);
  245.                 else {
  246.                     if (i <= M) {
  247.                         tmp = MkNode(t -> t_dat [2 * M - 1], (BTREE) NULL, t -> t_ptr [2 * M]);
  248.                         t -> t_active--;
  249.                         InsInNode(t, ins, NewNode);
  250.                     } else
  251.                         tmp = MkNode(ins, (BTREE) NULL, NewNode);
  252.                     /*
  253.                      *    Move keys and pointers ...
  254.                      */
  255.  
  256.                     for (j = M + 2; j <= 2 * M; ++j)
  257.                         InsInNode(tmp, t -> t_dat [j-1], t -> t_ptr [j]);
  258.  
  259.                     t -> t_active = M;
  260.                     tmp -> t_ptr [0] = t -> t_ptr [M+1];
  261.                     NewNode = tmp;
  262.  
  263.                     return t -> t_dat [M];
  264.                 }
  265.         }
  266.         return NullDatum;
  267.     }
  268. }
  269. /*
  270. **  INSERT -- Put a key into the B-tree
  271. **
  272. **    Enter the given key into the
  273. **    B-tree.
  274. **
  275. **    Parameters:
  276. **        key  --  Key value to enter.
  277. **
  278. **    Returns:
  279. **        Reference to the new B-tree.
  280. **
  281. */
  282.  
  283. BTREE
  284. Insert(dtm, t)
  285. DATUM    dtm;
  286. BTREE    t;{
  287.     DATUM    ins;
  288.  
  289.     ins = InternalInsert(dtm, t);
  290.  
  291.     /*
  292.      *    Did the root grow ?
  293.      */
  294.  
  295.     return KeyCmp(ins . key, NullDatum . key) != 0 ? MkNode(ins, t, NewNode) : t;
  296. }
  297. /*
  298. **  DELETE -- Remove a key from a B-tree
  299. **
  300. **    Remove the data associated with a
  301. **    given key from a B-tree.
  302. **
  303. **    Parameters:
  304. **        key  --  Key to use,
  305. **        t    --  B-tree to update.
  306. **
  307. **    Returns:
  308. **        Reference to the updated B-tree.
  309. **
  310. **    Notes:
  311. **        Real work is done by RealDelete() q.v.
  312. **
  313. */
  314.  
  315. static int    hadit = FALSE;
  316.  
  317. BTREE
  318. Delete(key, t)
  319. KEY    key;
  320. BTREE    t;{
  321.     BTREE    savet;
  322.  
  323.     RealDelete(key, t);
  324.  
  325.     if (!hadit) {
  326.         Error("No such key\n");
  327.         return NULL;
  328.     } else if (t -> t_active == 0) {    /* Root is now empty */
  329.         savet = t -> t_ptr [0];
  330.         Dispose(t);
  331.         return savet;
  332.     } else
  333.         return t;
  334. }
  335.  
  336. /*
  337. **  SEARCHNODE -- Find a key in a node
  338. **
  339. **    Look for a key in a single B-tree
  340. **    node.
  341. **
  342. **    Parameters:
  343. **        key  --  Key to look for,
  344. **        t    --  Ptr to B-tree node.
  345. **
  346. **    Returns:
  347. **        Index of matching key.
  348. **
  349. */
  350.  
  351. int
  352. SearchNode(key, t)
  353. KEY    key;
  354. BTREE    t;{
  355.     int    i;
  356.  
  357.     if (KeyCmp(key, t -> t_dat [0] . key) < 0) {
  358.         hadit = FALSE;
  359.         return 0;
  360.     } else {
  361.         for (i = t -> t_active; KeyCmp(key, t -> t_dat [i-1] . key) < 0 && i > 1; --i)
  362.             ;        /* NULL BODY */
  363.         hadit = (KeyCmp(key, t -> t_dat [i-1] . key) == 0);
  364.  
  365.         return i;
  366.     }
  367. }
  368. /*
  369. **  REALDELETE -- Remove a key from a tree
  370. **
  371. **    The business end of the Delete() function.
  372. **
  373. **    Parameters:
  374. **        key  --  Key to use,
  375. **        t    --  Tree to update.
  376. **
  377. **    Returns:
  378. **        None.
  379. **
  380. */
  381.  
  382. RealDelete(key, t)
  383. KEY    key;
  384. BTREE    t;{
  385.     int    k;
  386.  
  387.     if (t == NULL)
  388.         hadit = FALSE;
  389.     else {
  390.         k = SearchNode(key, t);
  391.  
  392.         if (hadit) {
  393.             if (t -> t_ptr [k-1] == NULL)        /* A leaf */
  394.                 Remove(t, k);
  395.             else {
  396.                 Succ(t, k);
  397.                 RealDelete(t -> t_dat [k-1] . key, t -> t_ptr [k]);
  398.                 if (!hadit)
  399.                     Error("Hmm ???");
  400.             }
  401.         } else {
  402.             RealDelete(key, t -> t_ptr [k]);
  403.  
  404.             if (t -> t_ptr [k] != NULL && t -> t_ptr [k] -> t_active < M)
  405.                 Restore(t, k);
  406.         }
  407.     }
  408. }
  409.  
  410. /*
  411. **  REMOVE -- Remove a single datum
  412. **
  413. **    Remove a datum from a B-tree node
  414. **    by shuffling down the pointers and
  415. **    data above it.
  416. **
  417. **    Parameters:
  418. **        t   --  Ptr to the B-tree node,
  419. **        pos --  Index of the key to be removed.
  420. **
  421. **    Returns:
  422. **        None.
  423. **
  424. */
  425.  
  426. Remove(t, pos)
  427. BTREE    t;
  428. int    pos;{
  429.     int    i;
  430.  
  431.     for (i = pos + 1; i <= t -> t_active; ++i) {
  432.         t -> t_dat [i-2] = t -> t_dat [i-1];
  433.         t -> t_ptr [i-1] = t -> t_ptr [i];
  434.     }
  435.     t -> t_active--;
  436. }
  437.  
  438. /*
  439. **  SUCC -- Replace a key by its successor
  440. **
  441. **    Using the natural ordering, replace
  442. **    a key wit